#include <tinx/list.h>
#include <tinx/string.h>

void list_init(list_t *list)
{
    list->head.next = &list->tail;
    list->head.prev = NULL;
    list->tail.next = NULL;
    list->tail.prev = &list->head;
}

void list_insert(list_node_t *before, list_node_t *node)
{
    before->prev->next = node;
    node->prev = before->prev;
    before->prev = node;
    node->next = before;
}

void list_remove(list_node_t *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
    memset(node, 0, sizeof(list_node_t));
}

list_node_t *list_pop(list_t *list)
{
    list_node_t *node = list->head.next;
    if (node == &list->tail)
    {
        return NULL;
    }
    list_remove(node);
    return node;
}

list_node_t *list_popback(list_t *list)
{
    list_node_t *node = list->tail.prev;
    if (node == &list->head)
    {
        return NULL;
    }
    list_remove(node);
    return node;
}

void list_push(list_t *list, list_node_t *node)
{
    list_insert(list->head.next, node);
}

void list_append(list_t *list, list_node_t *node)
{
    list_insert(&list->tail, node);
}

bool list_find(list_t *list, list_node_t *node)
{
    for ( list_node_t *ptr = list->head.next; ptr != &list->tail; ptr = ptr->next)
    {
        if (ptr == node)
        {
            return true;
        }
    }
    return false;
}

bool list_empty(list_t *list)
{
    if (list->head.next == &list->tail)
    {
        return true;
    }
    return false;
}

int list_size(list_t *list)
{
    list_node_t *ptr = list->head.next;
    int length = 0;
    while (true)
    {
        if (ptr == &list->tail)
            return length;

        length++;
        ptr = ptr->next;
    }
}

// 链表插入排序
void list_insert_sort(list_t *list, list_node_t *node, int offset)
{
    list_node_t *before = &list->tail;
    int key = element_node_key(node, offset);

    for (list_node_t *ptr = list->head.next; ptr != &list->tail; ptr = ptr->next)
    {
        int compare = element_node_key(ptr, offset);
        if (compare > key)
        {
            before = ptr;
        }
    }
    list_insert(before, node);
}